package datastructure.structure;


import java.util.logging.Logger;

/**
 * 红黑树 (仅有插入操作)
 *
 * @author or2
 * @cr 2021/8/9 11:50
 */
public class BRTree<E extends Comparable<E>> {

    private static final Logger logger = Logger.getLogger(BRTree.class.getName());

    /**
     * 数结点-数据结构
     */
    private class Node {
        /**
         * 结点的值
         */
        E value;
        /**
         * 结点的左右孩子
         */
        Node lChild, rChild;
        /**
         * 当前树的高度
         */
        int height;
        /**
         * 当前结点的颜色
         */
        private Color color;

        public Node(E value) {
            this.value = value;
            this.lChild = null;
            this.rChild = null;
            this.height = 1;
//            初始红色, 默认合并处理
            this.color = Color.RED;
        }
    }

    /**
     * 树的根节点
     */
    private Node root;
    /**
     * 当前树的总结点数目
     */
    private int size;

    /**
     * 获取当前结点的高度
     *
     * @param node 检测结点
     * @return 非空时 - 当前结点的高度<br/>为空时空 - 返回高度 0
     */
    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    /**
     * 判断该节点的颜色
     *
     * @param node 判断的结点
     * @return 红色 -> true<br/>
     * 空结点 or 结点为黑色 -> false
     */
    private boolean isRed(Node node) {
//        空结点 (叶子节点) 都是黑色的
        if (node == null) {
            return false;
        }
        return node.color == Color.RED;
    }

    /**
     * 当前结点平衡因子是否满足要求
     *
     * @param node 检测结点
     * @return {@code n > 0} - 左子树比右子树高 n<br/>{@code n = 0} - 左子树与右子树一样高<br/>{@code n < 0} - 左子树比右子树矮 n
     */
    private int isBalanced(Node node) {
        int lHeight = getHeight(node.lChild);
        int rHeight = getHeight(node.rChild);
        return lHeight - rHeight;
    }

    /**
     * 向红黑树中添加一个结点
     *
     * @param value 新添加的值
     * @return 自身->链式调用
     */
    public BRTree<E> add(E value) {
        if (size == 0) {
            root = new Node(value);
            size++;
        } else {
            root = addRecursion(root, value);
        }
//        保持根节点为黑色
        root.color = Color.BLACK;
        return this;
    }

    /**
     * 递归算法: 检测当前 cNode 的结点添加新元素
     *
     * @param cNode 当前检测的结点
     * @param value 新元素的值
     */
    private Node addRecursion(Node cNode, E value) {
        if (cNode == null) {
            size++;
//            默认插入红色结点
            return new Node(value);
        }

        int compareTo = value.compareTo(cNode.value);
//        不允许重复插入
        if (compareTo == 0) {
            return cNode;
        }
//        按条件递归检测孩子结点
        if (compareTo < 0) {
            cNode.lChild = addRecursion(cNode.lChild, value);
        } else {
            cNode.rChild = addRecursion(cNode.rChild, value);
        }

//        状态 ①
        if (isRed(cNode.rChild) && !isRed(cNode.lChild)) {
            cNode = leftRotate(cNode);
        }
//        状态 ②
        if (isRed(cNode.lChild) && isRed(cNode.lChild.lChild)) {
            cNode = rightRotate(cNode);
        }
//        状态 ③
        if (isRed(cNode.lChild) && isRed(cNode.rChild)) {
            filpColors(cNode);
        }

//        插入后开始更新当前结点高度
        cNode.height = Math.max(getHeight(cNode.lChild), getHeight(cNode.rChild)) + 1;
//        检测当前结点表示的子树是否仍是平衡二叉树
        return cNode;
    }

    /**
     * <pre>{@code
     * |————————————————————————————————————————————————————————|
     * |            对结点y进行左旋操作, 返回旋转后的根节点x           |
     * |          y                                 x           |
     * |         / \                               / \          |
     * |       T1   x         向左旋转 (y)         y    z         |
     * |           / \      ———————————————>    / \   / \       |
     * |          T2  z                        T1 T2 T3 T4      |
     * |             / \                                        |
     * |            T3  T4                                      |
     * |————————————————————————————————————————————————————————|
     *  }</pre>
     *
     * @param cNode 最小不符合 平衡二叉树的子树的 根节点
     * @return 旋转后子树的根节点
     */
    private Node leftRotate(Node cNode) {
        Node x = cNode.rChild;
//        向左旋转
        cNode.rChild = x.lChild;
        x.lChild = cNode;
//        更新颜色
        x.color = cNode.color;
        cNode.color = Color.RED;
//        更新高度
        cNode.height = Math.max(getHeight(cNode.lChild), getHeight(cNode.rChild)) + 1;
        x.height = Math.max(getHeight(x.lChild), getHeight(x.rChild)) + 1;

        return x;
    }

    /**
     * 颜色翻转 (向上合并)
     *
     * @param node 当前树的根节点
     */
    private void filpColors(Node node) {
        node.color = Color.RED;
        node.lChild.color = Color.BLACK;
        node.rChild.color = Color.BLACK;
    }

    /**
     * <pre>{@code
     * |————————————————————————————————————————————————————————|
     * |            对结点y进行右旋操作, 返回旋转后的根节点x           |
     * |            y                               x           |
     * |           / \                             / \          |
     * |          x   T4     向右旋转 (y)          z    y         |
     * |         / \       ———————————————>     / \   / \       |
     * |        z   T3                         T1 T2 T3 T4      |
     * |       / \                                              |
     * |      T1  T2                                            |
     * |————————————————————————————————————————————————————————|
     *  }</pre>
     *
     * @param cNode 最小不符合 平衡二叉树的子树的 根节点
     * @return 旋转后子树的根节点
     */
    private Node rightRotate(Node cNode) {
        Node x = cNode.lChild;
//        右旋
        cNode.lChild = x.rChild;
        x.rChild = cNode;
//        更新颜色
        x.color = cNode.color;
        cNode.color = Color.RED;
//        更新高度
        cNode.height = Math.max(getHeight(cNode.lChild), getHeight(cNode.rChild)) + 1;
        x.height = Math.max(getHeight(x.lChild), getHeight(x.rChild)) + 1;
        return x;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        int leafNodesNum = (int) (Math.pow(2, Math.log(size) / Math.log(2)));

        generateString(root, 0, stringBuilder, leafNodesNum);

        return stringBuilder.toString();
    }

    /**
     * 生成方便观看的BST
     *
     * @param root          当前结点做根节点, 不断递归
     * @param depth         当前深度, 每次递归 +1
     * @param stringBuilder 拼接字符串用
     * @param leafNodesNum  防止重复计算, 第一次计算后一直传递
     */
    private void generateString(Node root, int depth, StringBuilder stringBuilder, int leafNodesNum) {
        double section = Math.pow(2, depth) + 1;
        int sectionLength = (int) (leafNodesNum / section);
        String gap = "\t".repeat(sectionLength);

        if (root == null) {
            stringBuilder.append(gap).append("空").append("\n");
            return;
        }

        generateString(root.lChild, depth + 1, stringBuilder, leafNodesNum);
        stringBuilder.append(gap).append(root.value).append("\n");
        generateString(root.rChild, depth + 1, stringBuilder, leafNodesNum);
    }

    private enum Color {
        RED,
        BLACK;
    }
}
